<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
  <head>
    <title>Introduction to the Theory of Computation</title>
    <meta name="generator" content="Muse">
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
    
    <link rel="stylesheet" type="text/css"charset="utf-8" media="all" href="../styles/common.css"  />

    <script src="../scripts/jsMath/easy/load.js"></script>
  </head>

  <body>

    <h1>Introduction to the Theory of Computation
      <!-- menu start here -->
      <div class="menu">
        <div class="menuitem">
          <a href="../home/index.html">Home</a>
        </div>
        <div class="menuitem">
          <a href="../courses/index.html">Courses</a>
        </div>
        <div class="menuitem">
          <a href="../projects/index.html">Projects</a>
        </div>
        <div class="menuitem">
          <a href="../complang/index.html">CompLang</a>
        </div>
        <div class="menuitem">
          <a href="../code/index.html">CodeReading</a>
        </div>
        <div class="menuitem">
          <a href="../software/index.html">Software</a>
        </div>
        <div class="menuitem">
          <a href="../lectures/index.html">Lectures</a>
        </div>
      </div>
      <!-- menu ends here -->

    </h1>


    <!-- Page published by Emacs Muse begins here -->

<div class="contents">
<dl>
<dt>
<a href="#sec1">Regular Languages</a>
</dt>
<dd>
<dl>
<dt>
<a href="#sec2">Pumping lemma for regular languages</a>
</dt>
</dl>
</dd>
</dl>
</div>


<h2><a name="sec1" id="sec1"></a>
Regular Languages</h2>

<h3><a name="sec2" id="sec2"></a>
Pumping lemma for regular languages</h3>

<p class="first">If A is a regular languag, then there is a number <em>p</em> (the pumping
length) where, if <em>s</em> is any string in A of length at least <em>p</em>, then <em>s</em>
may be divided into three pieces, <em>s = xyz</em>, satisfying the following
conditions:


<div class="math">
. for each i \ge 0, xy^iz \in A,
</div></p>




<!-- Page published by Emacs Muse ends here -->
<hl />
<p />
<!-- <center> -->
<!--   Updated at  -->
<!--   2010-03-21 -->
<!-- </center> -->

<script type="text/javascript">
  var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
  document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
</script>
<script type="text/javascript">
  try {
  var pageTracker = _gat._getTracker("UA-2241833-12");
  pageTracker._trackPageview();
  } catch(err) {}</script>

</body>
</html>

